Network congestion occurs when a link or node in the network is required to carry more data traffic than it is capable of transmitting or forwarding, with the result that its quality of service deteriorates. Typical effects of congestion include queueing delay, packet loss, and blocking of new connections. Modern packet networks use congestion control (including congestion avoidance) techniques to try to mitigate congestion before catastrophic results set in.
A number of congestion avoidance techniques are known in the art. In random early detection (RED, also known as random early discard or random early drop), for example, network nodes, such as switches, monitor their average queue size and drop packets based on statistical probabilities: If a given queue (or set of queues) is almost empty, all incoming packets are accepted. As the queue grows, the probability of dropping an incoming packet grows accordingly, reaching 100% when the buffer is full. Weighted RED (WRED) works in a similar fashion, except that different traffic classes are assigned different thresholds, so that for a given queue length, low-priority packets have a greater probability of being dropped than high-priority packets. Congestion control techniques of this sort, which operate on a fraction of packets that is determined by statistical probabilities, are referred to herein as statistical congestion control techniques.
Another congestion avoidance technique is Explicit Congestion Notification (ECN), which is an extension to the Internet Protocol (IP) and the Transmission Control Protocol (TCP). ECN was initially defined by Ramakrishnan, et al., in “The Addition of Explicit Congestion Notification (ECN) to IP,” which was published as Request for Comments (RFC) 3168 of the Internet Engineering Task Force (2001) and is incorporated herein by reference. ECN provides end-to-end notification of network congestion without dropping packets, by signaling impending congestion in the IP header of transmitted packets. The receiver of an ECN-marked packet of this sort echoes the congestion indication to the sender, which reduces its transmission rate as though it had detected a dropped packet. ECN functionality has recently been extended to other transport and tunneling protocols.
In shared-memory switching architectures, the queues for multiple interfaces of a network element (such as ports of a switch) are maintained in a common memory buffer. Each queue is assigned a certain maximum fraction of the memory, wherein the sum of all the fractions may be greater than one in order to take full advantage of the available memory. In some buffer management schemes of this sort, the fractional shares of the different queues are not fixed, but rather are defined dynamically, meaning that the maximum permissible length of any given queue (above which packets are dropped from the queue) varies over time, depending on the overall occupancy of the buffer. In other words, when the shared buffer is relatively empty, the maximum permitted queue length increases, and this maximum length decreases as the buffer fills.
Hahne and Choudhury, for example, describe a scheme of this sort in “Dynamic Queue Length Thresholds for Multiple Loss Priorities,” IEEE/ACM Transactions on Networking 10:3 (June, 2002), pages 368-380, which is incorporated herein by reference. According to this scheme, the maximum permissible queue length in a shared-memory packet switch is proportional to the unused buffering in the switch. Each queue receives a certain amount of buffer space, called the “control threshold,” and incoming data cells are admitted to the switch only if the queue length is less than the control threshold. The control threshold T(t) for each queue t is proportional to the amount of space in the buffer that is currently unused, with a proportionality constant α:
      T    ⁡          (      t      )        =            α      ⁡              (                  B          -                      Q            ⁡                          (              t              )                                      )              =          α      (              B        -                              ∑            i                    ⁢                                          ⁢                                    Q              i                        ⁡                          (              t              )                                          )      Here B is the total buffer size, and Q(t) is the aggregate amount of space occupied in the buffer by all of the queues, each of which occupies the respective space Qi(t).